package DataStructure.graph;

import DataStructure.linear.Stack;

public class DepthFirstOrder {
    //记录是否已经被搜索
    private boolean[] marked;
    //使用栈存储顶点序列
    private Stack<Integer> reversePost;

    //创建一个检测环对象，
    public DepthFirstOrder(Digraph G){
        this.marked=new boolean[G.V()];
        this.reversePost=new Stack<Integer>();

        //遍历图中每一个顶点，让每个顶点作为入口完成一次深度优先搜索
        for (int v = 0; v < G.V(); v++) {
            if(!marked[v]){
                dfs(G,v);
            }
        }
    }

    //基于深度优先搜索把顶点排序
    public void dfs(Digraph G,int v){
        marked[v]=true;
        for (Integer w : G.adj(v)) {
            if(!marked[w]){
                dfs(G,w);
            }
        }
        //让顶点v进栈
        reversePost.push(v);
    }

    //获取顶点线性序列
    public Stack<Integer> ReversePost(){
        return reversePost;
    }
}
